package com.leecode;

/**
 * 142. 环形链表 II
 *
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 *
 * 说明：不允许修改给定的链表。
 *
 * 进阶：
 *
 *     你是否可以使用 O(1) 空间解决此题？
 *
 *
 *
 * 示例 1：
 *
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：返回索引为 1 的链表节点
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 */
public class Leet142 {
	public static void main(String[] args) {
//		ListNode listNode3 = new ListNode(3);
//		ListNode listNode2 = new ListNode(2);
//		listNode3.next=listNode2;
//		ListNode listNode0 = new ListNode(0);
//		listNode2.next=listNode0;
//		ListNode listNode4 = new ListNode(4);
//		listNode0.next=listNode4;
//		listNode4.next=listNode2;
//		new Leet142().detectCycle(listNode3);

//		ListNode listNode1 = new ListNode(1);
//		ListNode listNode2 = new ListNode(2);
//		listNode1.next=listNode2;
//		listNode2.next=listNode1;
//		new Leet142().detectCycle(listNode1);


//		new Leet142().detectCycle(listNode1);
	}

	/**
	 * 数学证明.环前节点a个,环节点b个
	 * q=2s     只要开始走动,就符合这个公式,走一次符合,走两次符合,走到第一次相遇同样符合,走到第二次相遇也同样符合.
	 * q=s+nb   第二次相遇时,q比s多走n圈,这不难理解
	 * s=nb
	 * target=a+nb
	 * 问题转化为:第二次相遇时.s在nb处,s再走a次,target就是环入口,如何才能再走a步??!!
	 * bug3:这代码还能超时?!!!!!!!!!!!!!!!!!!
	 */
	public ListNode detectCycle2(ListNode head) {
		if(head==null || head.next==null)return null;

		ListNode slow=head,quic=head;
		int count=-1;
		while(quic!=null){
			if(slow==quic)count++;
			if(count==1){
				if(slow==head)return slow;//bug2:第一次相遇在head,连a都不走了!!
				quic=head;
			}
			if(count==2)return slow;

			if(quic.next==null||quic.next.next==null||slow.next==null)break;
			quic=count<1?quic.next.next:quic.next;//bug:第一次相遇后,记得quic的速度要放慢
			slow=slow.next;
		}

		return null;
	}

	public ListNode detectCycle(ListNode head) {

		return null;
	}

}
